package com.sise.Linked;

/**
 *      206. 反转链表
 */
public class _206_reverseList {

    /**
     *      迭代 => 记录 pre、cur、next
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;

        while (cur != null) {
            next = cur.next;        // 保存下一个节点，因为等下 指向改变就会被断开
            cur.next = pre;         // 将当前节点 指向 上一个节点 pre <- cur
            pre = cur;              // 将当前节点 赋值 上一个节点 => 上一个节点往前一步
            cur = next;             // 将下一个节点 赋值 当前节点 => 当前节点往前一步
        }
        return pre;
    }

    /**
     * 递归
     */
    public ListNode reverseList_2(ListNode head) {
        if (head == null || head.next == null) return head;     // 直到当前节点的下一个节点为空时返回当前节点。由于 5 没有下一个节点了，所以此处返回节点 5。注意这里返回的是 head
        ListNode newHead = reverseList_2(head.next);            // 这里的 head = 4，但输入的 head.next = 5，递归返回的也是 5
        head.next.next = head;                                  // 4.next.next = 4 等同于 4 <- 5
        head.next = null;                                       // 让 4 指向空， null <- 4 <- 5
        return newHead;                                         // 递归会一直返回 5，直到递归结束
    }
}
